#include "Heap.h"

// 堆的初始化

void HPInit (HP* php)
{

    php -> arr = NULL ;

    php -> capacity = php -> size = 0 ;

}

// 堆的销毁

void HPDestory (HP* php)
{

    if (php -> arr)
    {

        free (php -> arr) ;

    }

    php -> arr = NULL ;

    php -> capacity = php -> size = 0 ;

}

// 堆的交换函数

void Swap (HPDataType* x , HPDataType* y)
{

    HPDataType tmp ;

    tmp = *x ;

    *x = *y ;

    *y = tmp ;

}

// 堆的向上调整算法

void AdjustUp (HPDataType* arr , int child)
{

    int parent = (child - 1) / 2 ;

    while (child > 0) // 从子节点一直向上调整到根节点,将大小顺序调整好为止
    {

        // 建大堆: >
        // 建小堆: <

        if (arr [child] > arr [parent])
        {

            // 调整

            Swap (&arr [child] , &arr [parent]) ;

            child = parent ;

            parent = (child - 1) / 2 ;

        }

        else
        {

            break ;

        }
        
    }
    
}

// 堆的向下调整算法

void AdjustDown (HPDataType* arr , int parent , int n)
{

    int child = parent / 2 + 1 ; // 先确定左孩子的位置(至少会有左孩子)

    while (child < n)
    {

        // 大堆: <
        // 小堆: >

        if (child + 1 < n && arr [child] < arr [child + 1]) // 判断右孩子是否存在,且是否右孩子比左孩子大 是就选择右孩子进行向下排序
        {

            child++ ; // 变成右孩子

        }

        // 大堆: >
        // 小堆: <

        if (arr [child] > arr [parent])
        {

            Swap (&arr [child] , &arr [parent]) ;

            parent = child ;

            child = parent / 2 + 1 ;

        }

        else
        {

            break ;

        }

    }
    
}

// 入队,和顺序表步骤相同

void HPPush (HP* php , HPDataType x)
{

    assert (php) ;

    // 判断空间

    if (php -> size == php -> capacity)
    {

        int newcapacity = php -> capacity == 0 ? 4 : 2 * php -> capacity ;

        HPDataType* tmp = (HPDataType*) realloc (php -> arr , sizeof (HPDataType) * newcapacity) ;

        if (tmp == NULL)
        {

            perror ("malloc fail!") ;

            exit (1) ;

        }

        php -> arr = tmp ;

        php -> capacity = newcapacity ;

    }

    php -> arr [php -> size] = x ;

    AdjustUp (php -> arr , php -> size) ;

    ++php -> size ;

}

// 出堆
// 这里的出堆指的是将堆头取出来,也就是树的最值
// 但是按照顺序表的结构,这个头并不好取出来(会涉及到数组的移动,很麻烦)
// 这里使用一种非常巧妙的方法: 将头和最后一个叶子节点交换,再让叶子节点向下调整,就可以以最小代价出堆了

void HPPop (HP* php)
{

    assert (!HPEmpty (php)) ;

    // (0) (php -> size - 1)

    Swap (&php -> arr [0] , &php -> arr [php -> size - 1]) ;

    --php -> size ;

    // 向下调整

    AdjustDown (php -> arr , 0 , php -> size) ;

}

// 判断堆是否为空

bool HPEmpty (HP* php)
{

    assert (php) ;

    return php -> size == 0 ;

}

// 取堆顶数据

HPDataType HPTop (HP* php)
{

    assert (!HPEmpty (php)) ;

    return php -> arr [0] ;

}

// 求堆大小

int HPSize (HP* php)
{

    assert (!HPEmpty (php)) ;

    return php -> size ;

}

// 打印堆的数据

void HPPrint (HP* php)
{

    assert (php) ;

    for (int i = 0 ; i < php -> size ; i++)
    {

        printf ("%d " , php -> arr [i]) ;

    }

    printf ("\n") ;

}